package leetcode.hot100;

@SuppressWarnings("all")
public class _647_回文子串_动态规划 {

    // 状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串
    // 状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false
    // 当只有一个字符时，比如 a 自然是一个回文串
    // 当有两个字符时，如果是相等的，比如 aa，也是一个回文串
    // 当有三个及以上字符时，比如 ababa 这个字符记作 "串1"，把两边的 a 去掉，也就是 bab 记作 "串2"
    // 可以看出只要 "串2" 是一个回文串，那么左右各多了一个 a 的 "串1" 必定也是回文串
    // 所以当 s[i]==s[j] 时，只需要看 dp[i+1][j-1] 是不是一个回文串
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        boolean[][] dp = new boolean[s.length()][s.length()];
        int all = 0;
        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                // j - i < 2表示区间字符少于等于三个，那么首位判断为true后一定是回文串
                // j - i < 2的判断帮助初始化字符串的前两个字符串的回文情况
                if (s.charAt(j) == s.charAt(i) && (j - i < 2 || dp[i + 1][j - 1])) {
                    // 以i为结尾的回文字串
                    dp[i][j] = true;
                    all++;
                }
            }
        }
        return all;
    }
}
